/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / web / genus.web

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 20 75 68 72 | 69 67 40 6d 70 69 2d 73 |From uhr|ig@mpi-s|
|00000010| 62 2e 6d 70 67 2e 64 65 | 20 54 75 65 20 4f 63 74 |b.mpg.de| Tue Oct|
|00000020| 20 31 32 20 31 34 3a 33 | 34 3a 30 33 20 31 39 39 | 12 14:3|4:03 199|
|00000030| 33 0a 54 6f 3a 20 73 74 | 65 66 61 6e 0a 43 6f 6e |3.To: st|efan.Con|
|00000040| 74 65 6e 74 2d 4c 65 6e | 67 74 68 3a 20 31 38 31 |tent-Len|gth: 181|
|00000050| 35 0a 58 2d 4c 69 6e 65 | 73 3a 20 38 30 0a 0a 5c |5.X-Line|s: 80..\|
|00000060| 64 6f 63 75 6d 65 6e 74 | 73 74 79 6c 65 5b 31 31 |document|style[11|
|00000070| 70 74 2c 63 6f 6d 6d 65 | 6e 74 73 5d 7b 63 77 65 |pt,comme|nts]{cwe|
|00000080| 62 7d 0a 0a 5c 74 65 78 | 74 77 69 64 74 68 3d 36 |b}..\tex|twidth=6|
|00000090| 2e 35 69 6e 0a 5c 74 65 | 78 74 68 65 69 67 68 74 |.5in.\te|xtheight|
|000000a0| 3d 39 69 6e 0a 5c 6f 64 | 64 73 69 64 65 6d 61 72 |=9in.\od|dsidemar|
|000000b0| 67 69 6e 3d 30 69 6e 0a | 5c 74 6f 70 6d 61 72 67 |gin=0in.|\topmarg|
|000000c0| 69 6e 3d 30 69 6e 0a 0a | 5c 62 65 67 69 6e 7b 64 |in=0in..|\begin{d|
|000000d0| 6f 63 75 6d 65 6e 74 7d | 0a 0a 5c 6d 61 72 6b 72 |ocument}|..\markr|
|000000e0| 69 67 68 74 7b 5c 66 62 | 6f 78 7b 5c 70 72 6f 74 |ight{\fb|ox{\prot|
|000000f0| 65 63 74 5c 74 69 6e 79 | 20 76 65 72 73 69 6f 6e |ect\tiny| version|
|00000100| 20 6f 66 20 5c 74 6f 64 | 61 79 7d 7d 0a 5c 70 61 | of \tod|ay}}.\pa|
|00000110| 67 65 73 74 79 6c 65 7b | 6d 79 68 65 61 64 69 6e |gestyle{|myheadin|
|00000120| 67 73 7d 0a 0a 40 2a 20 | 54 68 65 20 47 65 6e 75 |gs}..@* |The Genu|
|00000130| 73 20 6f 66 20 61 6e 20 | 45 6d 62 65 64 64 69 6e |s of an |Embeddin|
|00000140| 67 2e 0a 4c 65 74 20 7c | 47 7c 20 62 65 20 61 20 |g..Let ||G| be a |
|00000150| 67 72 61 70 68 20 77 69 | 74 68 20 61 20 63 79 63 |graph wi|th a cyc|
|00000160| 6c 69 63 20 6f 72 64 65 | 72 69 6e 67 20 6f 6e 20 |lic orde|ring on |
|00000170| 74 68 65 20 65 64 67 65 | 73 20 69 6e 63 69 64 65 |the edge|s incide|
|00000180| 6e 74 20 74 6f 20 65 61 | 63 68 0a 76 65 72 74 65 |nt to ea|ch.verte|
|00000190| 78 2e 20 57 65 20 61 73 | 73 75 6d 65 20 7c 47 7c |x. We as|sume |G||
|000001a0| 20 74 6f 20 62 65 20 73 | 69 6d 70 6c 65 20 61 6e | to be s|imple an|
|000001b0| 64 20 62 69 64 69 72 65 | 63 74 65 64 2e 20 28 54 |d bidire|cted. (T|
|000001c0| 68 69 73 20 70 72 65 63 | 6f 6e 64 69 74 69 6f 6e |his prec|ondition|
|000001d0| 0a 69 73 20 63 68 65 63 | 6b 65 64 20 61 6e 64 20 |.is chec|ked and |
|000001e0| 7c 2d 31 7c 20 69 73 20 | 72 65 74 75 72 6e 65 64 ||-1| is |returned|
|000001f0| 20 69 66 20 69 74 20 69 | 73 20 76 69 6f 6c 61 74 | if it i|s violat|
|00000200| 65 64 29 2e 20 57 65 20 | 63 6f 6d 70 75 74 65 20 |ed). We |compute |
|00000210| 74 68 65 0a 67 65 6e 75 | 73 20 6f 66 20 7c 47 7c |the.genu|s of |G||
|00000220| 20 61 63 63 6f 72 64 69 | 6e 67 20 74 6f 20 45 75 | accordi|ng to Eu|
|00000230| 6c 65 72 27 73 0a 0a 5c | 5b 20 67 20 3d 20 28 6d |ler's..\|[ g = (m|
|00000240| 2d 6e 2d 66 2b 63 2b 31 | 29 2f 32 5c 5d 0a 0a 48 |-n-f+c+1|)/2\]..H|
|00000250| 65 72 65 20 7c 6e 7c 20 | 69 73 20 74 68 65 20 6e |ere |n| |is the n|
|00000260| 75 6d 62 65 72 20 6f 66 | 20 76 65 72 74 69 63 65 |umber of| vertice|
|00000270| 73 20 6f 66 20 7c 47 7c | 2c 20 7c 6d 7c 20 69 73 |s of |G||, |m| is|
|00000280| 20 74 68 65 20 6e 75 6d | 62 65 72 20 6f 66 20 0a | the num|ber of .|
|00000290| 75 6e 64 69 72 65 63 74 | 65 64 20 65 64 67 65 73 |undirect|ed edges|
|000002a0| 20 6f 66 20 7c 47 7c 2c | 20 7c 66 7c 20 69 73 20 | of |G|,| |f| is |
|000002b0| 74 68 65 20 6e 75 6d 62 | 65 72 20 6f 66 20 66 61 |the numb|er of fa|
|000002c0| 63 65 73 20 6f 66 20 7c | 47 7c 20 61 6e 64 20 0a |ces of ||G| and .|
|000002d0| 7c 63 7c 20 69 73 20 74 | 68 65 20 6e 75 6d 62 65 ||c| is t|he numbe|
|000002e0| 72 20 6f 66 20 63 6f 6e | 6e 65 63 74 65 64 20 63 |r of con|nected c|
|000002f0| 6f 6d 70 6f 6e 65 6e 74 | 73 20 6f 66 20 7c 47 7c |omponent|s of |G||
|00000300| 2e 20 41 20 66 61 63 65 | 20 63 61 6e 20 62 65 20 |. A face| can be |
|00000310| 74 72 61 63 65 64 0a 62 | 79 20 73 74 61 72 74 69 |traced.b|y starti|
|00000320| 6e 67 20 61 74 20 61 6e | 20 61 72 62 69 74 72 61 |ng at an| arbitra|
|00000330| 72 79 20 65 64 67 65 20 | 7c 65 30 7c 20 61 6e 64 |ry edge ||e0| and|
|00000340| 20 74 68 65 6e 20 63 6f | 6e 73 74 72 75 63 74 69 | then co|nstructi|
|00000350| 6e 67 20 61 20 70 61 74 | 68 20 61 73 0a 66 6f 6c |ng a pat|h as.fol|
|00000360| 6c 6f 77 73 2e 20 57 68 | 65 6e 20 61 20 76 65 72 |lows. Wh|en a ver|
|00000370| 74 65 78 20 69 73 20 65 | 6e 74 65 72 65 64 20 74 |tex is e|ntered t|
|00000380| 68 72 6f 75 67 68 20 65 | 64 67 65 20 7c 65 7c 20 |hrough e|dge |e| |
|00000390| 74 68 65 6e 20 69 74 20 | 69 73 20 6c 65 66 74 0a |then it |is left.|
|000003a0| 74 68 72 6f 75 67 68 20 | 74 68 65 20 73 75 63 63 |through |the succ|
|000003b0| 65 73 73 6f 72 20 6f 66 | 20 72 65 76 65 72 73 61 |essor of| reversa|
|000003c0| 6c 20 6f 66 20 7c 65 7c | 2e 0a 0a 40 63 0a 0a 69 |l of |e||...@c..i|
|000003d0| 6e 74 20 67 65 6e 75 73 | 28 67 72 61 70 68 26 47 |nt genus|(graph&G|
|000003e0| 29 0a 0a 7b 20 65 64 67 | 65 5f 61 72 72 61 79 3c |)..{ edg|e_array<|
|000003f0| 65 64 67 65 3e 20 72 65 | 76 65 72 73 61 6c 28 47 |edge> re|versal(G|
|00000400| 29 3b 0a 0a 20 20 69 66 | 28 21 69 73 5f 73 69 6d |);..  if|(!is_sim|
|00000410| 70 6c 65 28 47 29 20 7c | 7c 20 21 69 73 5f 62 69 |ple(G) ||| !is_bi|
|00000420| 64 69 72 65 63 74 65 64 | 28 47 2c 72 65 76 65 72 |directed|(G,rever|
|00000430| 73 61 6c 29 29 0a 20 20 | 72 65 74 75 72 6e 20 2d |sal)).  |return -|
|00000440| 31 3b 0a 0a 20 20 69 6e | 74 20 63 3b 0a 20 20 40 |1;..  in|t c;.  @|
|00000450| 3c 64 65 74 65 72 6d 69 | 6e 65 20 6e 75 6d 62 65 |<determi|ne numbe|
|00000460| 72 20 6f 66 20 63 6f 6d | 70 6f 6e 65 6e 74 73 40 |r of com|ponents@|
|00000470| 3e 20 40 3b 0a 0a 20 20 | 69 6e 74 20 66 3d 20 30 |> @;..  |int f= 0|
|00000480| 3b 0a 20 20 40 3c 64 65 | 74 65 72 6d 69 6e 65 20 |;.  @<de|termine |
|00000490| 6e 75 6d 62 65 72 20 6f | 66 20 66 61 63 65 73 40 |number o|f faces@|
|000004a0| 3e 20 40 3b 0a 0a 20 20 | 72 65 74 75 72 6e 28 28 |> @;..  |return((|
|000004b0| 47 2e 6e 75 6d 62 65 72 | 5f 6f 66 5f 65 64 67 65 |G.number|_of_edge|
|000004c0| 73 28 29 2f 32 2d 28 47 | 2e 6e 75 6d 62 65 72 5f |s()/2-(G|.number_|
|000004d0| 6f 66 5f 6e 6f 64 65 73 | 28 29 29 2d 66 2b 63 2b |of_nodes|())-f+c+|
|000004e0| 31 29 2f 32 29 3b 0a 7d | 0a 0a 40 0a 54 68 65 20 |1)/2);.}|..@.The |
|000004f0| 66 6f 6c 6c 6f 77 69 6e | 67 20 63 6f 64 65 20 63 |followin|g code c|
|00000500| 6f 6d 70 75 74 65 73 20 | 74 68 65 20 6e 75 6d 62 |omputes |the numb|
|00000510| 65 72 20 7c 63 7c 20 6f | 66 20 63 6f 6e 6e 65 63 |er |c| o|f connec|
|00000520| 74 65 64 20 63 6f 6d 70 | 6f 6e 65 6e 74 73 2e 0a |ted comp|onents..|
|00000530| 0a 40 3c 64 65 74 65 72 | 6d 69 6e 65 20 6e 75 6d |.@<deter|mine num|
|00000540| 62 65 72 20 6f 66 20 63 | 6f 6d 70 6f 6e 65 6e 74 |ber of c|omponent|
|00000550| 73 40 3e 3d 0a 0a 20 20 | 6e 6f 64 65 5f 61 72 72 |s@>=..  |node_arr|
|00000560| 61 79 3c 69 6e 74 3e 20 | 63 6f 6d 70 6e 75 6d 28 |ay<int> |compnum(|
|00000570| 47 29 3b 0a 20 20 63 20 | 3d 20 43 4f 4d 50 4f 4e |G);.  c |= COMPON|
|00000580| 45 4e 54 53 28 47 2c 20 | 63 6f 6d 70 6e 75 6d 29 |ENTS(G, |compnum)|
|00000590| 3b 0a 0a 40 0a 49 74 20 | 72 65 6d 61 69 6e 73 20 |;..@.It |remains |
|000005a0| 74 6f 20 63 6f 6d 70 75 | 74 65 20 74 68 65 20 6e |to compu|te the n|
|000005b0| 75 6d 62 65 72 20 7c 66 | 7c 20 6f 66 20 66 61 63 |umber |f|| of fac|
|000005c0| 65 73 2e 0a 0a 40 3c 64 | 65 74 65 72 6d 69 6e 65 |es...@<d|etermine|
|000005d0| 20 6e 75 6d 62 65 72 20 | 6f 66 20 66 61 63 65 73 | number |of faces|
|000005e0| 40 3e 3d 0a 0a 20 20 65 | 64 67 65 5f 61 72 72 61 |@>=..  e|dge_arra|
|000005f0| 79 3c 62 6f 6f 6c 3e 20 | 72 65 61 63 68 65 64 28 |y<bool> |reached(|
|00000600| 47 2c 20 66 61 6c 73 65 | 29 3b 0a 20 20 65 64 67 |G, false|);.  edg|
|00000610| 65 20 65 2c 20 65 30 3b | 0a 0a 20 20 66 6f 72 61 |e e, e0;|..  fora|
|00000620| 6c 6c 5f 65 64 67 65 73 | 28 65 30 2c 20 47 29 0a |ll_edges|(e0, G).|
|00000630| 20 20 20 20 69 66 20 28 | 21 72 65 61 63 68 65 64 |    if (|!reached|
|00000640| 5b 65 30 5d 29 0a 20 20 | 20 20 20 20 7b 20 66 2b |[e0]).  |    { f+|
|00000650| 2b 3b 0a 09 40 3c 74 72 | 61 63 65 20 66 61 63 65 |+;..@<tr|ace face|
|00000660| 20 69 6e 63 69 64 65 6e | 74 20 74 6f 20 7c 65 30 | inciden|t to |e0|
|00000670| 7c 40 3e 20 40 3b 0a 20 | 20 20 20 20 20 7d 0a 0a ||@> @;. |     }..|
|00000680| 40 20 0a 57 65 20 74 72 | 61 63 65 20 74 68 65 20 |@ .We tr|ace the |
|00000690| 66 61 63 65 20 61 73 20 | 65 78 70 6c 61 69 6e 65 |face as |explaine|
|000006a0| 64 20 61 62 6f 76 65 2e | 0a 0a 40 3c 74 72 61 63 |d above.|..@<trac|
|000006b0| 65 20 66 61 63 65 20 69 | 6e 63 69 64 65 6e 74 20 |e face i|ncident |
|000006c0| 74 6f 20 7c 65 30 7c 40 | 3e 3d 0a 20 20 65 20 3d |to |e0|@|>=.  e =|
|000006d0| 20 47 2e 63 79 63 6c 69 | 63 5f 61 64 6a 5f 73 75 | G.cycli|c_adj_su|
|000006e0| 63 63 28 72 65 76 65 72 | 73 61 6c 5b 65 30 5d 29 |cc(rever|sal[e0])|
|000006f0| 3b 0a 20 20 77 68 69 6c | 65 20 28 65 20 21 3d 20 |;.  whil|e (e != |
|00000700| 65 30 29 0a 20 20 20 7b | 20 72 65 61 63 68 65 64 |e0).   {| reached|
|00000710| 5b 65 5d 20 3d 20 74 72 | 75 65 3b 20 0a 20 20 20 |[e] = tr|ue; .   |
|00000720| 20 20 65 20 3d 20 47 2e | 63 79 63 6c 69 63 5f 61 |  e = G.|cyclic_a|
|00000730| 64 6a 5f 73 75 63 63 28 | 72 65 76 65 72 73 61 6c |dj_succ(|reversal|
|00000740| 5b 65 5d 29 3b 20 0a 20 | 20 20 7d 0a 20 20 72 65 |[e]); . |  }.  re|
|00000750| 61 63 68 65 64 5b 65 30 | 5d 20 3d 20 74 72 75 65 |ached[e0|] = true|
|00000760| 3b 0a 20 20 0a 40 0a 5c | 65 6e 64 7b 64 6f 63 75 |;.  .@.\|end{docu|
|00000770| 6d 65 6e 74 7d 0a 0a    |                         |ment}.. |        |
+--------+-------------------------+-------------------------+--------+--------+